#include <iostream>
#include <stack>
#include <BinaryTree.hpp>

using namespace std;

class Solution
{
public:
    //TODO: this can be accelerated by hashmap
    bool isPrevious(const vector<int> &inorder, int val1, int val2)
    {
        for (const int val : inorder)
        {
            if (val == val1)
            {
                return true;
            }
            else if (val == val2)
            {
                return false;
            }
        }
        throw "not found";
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        stack<TreeNode *> stack;
        TreeNode *root = new TreeNode(preorder[0]);
        stack.push(root);
        for (int i = 1; i < preorder.size(); i++)
        {
            int inval = preorder[i];
            if (isPrevious(inorder, inval, stack.top()->val))
            {
                stack.top()->left = new TreeNode(inval);
                stack.push(stack.top()->left);
            }
            else
            {
                // be a right node of someone in stack
                TreeNode *last = nullptr;
                while (!isPrevious(inorder, inval, stack.top()->val))
                {
                    last = stack.top();
                    stack.pop();
                    if(stack.empty())
                        break;
                }
                last->right = new TreeNode(inval);
                stack.push(last->right);
            }
        }
        return root;
    }
};

int main()
{
    cout << "Code105" << endl;
    Solution s;
    vector<int> preorder{3, 9, 20, 15, 7};
    vector<int> inorder{9, 3, 15, 20, 7};
    TreeNode *root = s.buildTree(preorder, inorder);
    PrintTreeByWide(root, "null", 3);
    delete root;
    return 0;
}